package com.varbal.icegame.algorithms.example;

import org.springframework.stereotype.Component;

/**
 * 最大子列和问题
 * 整数序列【A1,A2,...An】，求子列中和最大的子列及其值
 */
@Component
public class MaxSubseqSum {

    /**
     * planA-从左到右依次加，比较后取最大
     * 时间复杂度T(n) = O(n^3)
     * @param A
     * @param n
     * @return
     */
    public int maxSubseqSum_1(int[] A , int n){
        int maxSum =0 , thisSum ;
        int i,j,k;
        for (i = 0 ; i < n ; i++){
            for (j = i ; j < n ; j++){
                thisSum = 0;
                for (k = i ; k <= j ; k++)
                    thisSum += A[k];
                if (thisSum > maxSum)
                    maxSum = thisSum;
            }
        }
        return maxSum;
    }

    /**
     * planB-改良A，去除掉k，在第二层循环内直接累计
     * 时间复杂度T(n) = O(n^2)
     * @param A
     * @param n
     * @return
     */
    public int maxSubseqSum_2(int[] A , int n){
        int maxSum =0 , thisSum ;
        int i,j;
        for (i = 0 ; i < n ; i++){
            thisSum = 0;
            for (j = i ; j < n ; j++){
                thisSum += A[j];
                if (thisSum > maxSum)
                    maxSum = thisSum;
            }
        }
        return maxSum;
    }

    /**待测试
     * planC-分而治之，将序列递归二分，逐层相加比较
     * 时间复杂度T(n) = O(Nlog^N)
     * @param A
     * @param n
     * @return
     */
    public int maxSubseqSum_3(int[] A , int n){
        int maxSubseqSum;
        int[] maxSubseqIndex = limitSubseqSum(A , n , 0 , n-1);
        int[] maxSubseq = subseq(A , maxSubseqIndex[0] , maxSubseqIndex[maxSubseqIndex.length-1]+1);
        maxSubseqSum = subseqSum(maxSubseq);
        return maxSubseqSum;
    }

    /**
     * planD-在线处理，直接顺序计算，哨兵记录最大和
     * 时间复杂度T(n) = O(N)
     * @param A
     * @param n
     * @return
     */
    public int maxSubseqSum_4(int[] A , int n){
        int maxSum = 0, thisSum = 0;
        int[] maxSubseqIndex , maxSubseq = null;
        for (int i = 0 ; i < A.length ; i++){
            thisSum += A[i];
            if (thisSum > maxSum)
                maxSum = thisSum;
            else if (thisSum < 0)
                thisSum = 0;
        }
        return maxSum;
    }

    /**
     * 递归取最大子列的下标
     * @param A
     * @param n
     * @param left
     * @param right
     * @return
     */
    public int[] limitSubseqSum(int[] A , int n , int left , int right){
        //左右子列的下标集合
        int[] leftMaxSubseq , rightMaxSubseq , maxSubseq = null;
        //继续拆分子列，直至最小单位
        if (n > 2){
            int leftNum = n / 2;
            int[] leftSubseq = subseq(A , 0 , leftNum);
            leftMaxSubseq = limitSubseqSum(leftSubseq , leftNum , left , left+leftNum - 1) ;
            int[] rightSubseq = subseq(A , leftNum , n );
            rightMaxSubseq = limitSubseqSum(rightSubseq , n - leftNum , left + leftNum , right);
        }else {
            leftMaxSubseq = new int[]{left};
            rightMaxSubseq = new int[]{right};
        }
//      获取左子列的数据
        int[] leftSubseq = subseq(A ,leftMaxSubseq[0] - left ,n - (right - leftMaxSubseq[leftMaxSubseq.length-1]));
//      求左子列的和
        int leftSubseqSum = subseqSum(leftSubseq);

//      获取右子列的数据
        int[] rightSubseq = subseq(A ,rightMaxSubseq[0] - left ,n - (right - rightMaxSubseq[rightMaxSubseq.length-1]));
//      求右子列的和
        int rightSubseqSum = subseqSum(rightSubseq);

        //获取从左子列到右子列的中央子列
        int[] centerSubseq = subseq(A , leftMaxSubseq[0] - left , n - (right - rightMaxSubseq[rightMaxSubseq.length-1]));
        //中央子列下标的集合
        int[] centerMaybeMaxSubseq = join(leftMaxSubseq[0] , rightMaxSubseq[rightMaxSubseq.length-1]);
        //求中央子列的和
        int centerSubseqSum = subseqSum(centerSubseq);

        //取最大子列和
        if (leftSubseqSum >= rightSubseqSum){
            maxSubseq = leftSubseqSum >= centerSubseqSum ? leftMaxSubseq : centerMaybeMaxSubseq;
        }
        else {
            maxSubseq = centerSubseqSum >= rightSubseqSum ? centerMaybeMaxSubseq : rightMaxSubseq;
        }
        return maxSubseq;
    }

    /**
     * 取下标为集合
     * @param left
     * @param right
     * @return
     */
    public int[] join(int left , int right){
        int[] sub = null;
        int length = right - left + 1;
        if (right > left){
            sub = new int[length];
            for (int i = 0 ,j = left; i < length ; i++ , j++){
                sub[i] = j ;
            }
        }
        return sub;
    }
    /**
     * 获取列和
     * @param A
     * @return
     */
    public int subseqSum(int[] A){
        int i = A.length;
        int sum = 0 ;
        for (int j = 0 ; j < i ; j++){
            sum += A[j];
        }
        return sum;
    }
    /**
     * 截取子列
     * 左闭右开
     * @param M
     * @param left
     * @param right
     * @return
     */
    public int[] subseq(int[] M , int left , int right){
        int[] n = new int[right - left];
        int num = 0;
        for (int i = left;i < right ; i++){
            n[num] = M[i];
            num++;
        }
        return n;
    }

//    public static void main(String[] args) {
//        int[] A = {35,-21,41,-24,-13,31,51,-13,-21,35,63,-21};
//        System.out.println(new MaxSubseqSum().maxSubseqSum_3(A,A.length));
//    }
}
